import java.util.Arrays;

public class SlidingWindowsCounter implements LimitedCounter {

    //窗口最左端的计数器的时间戳
    private volatile long preTimeStamp;
    //窗口
    private int[] windows;
    //一个窗口单元格的时间长度
    private int timeSlice;
    //窗口内的最大计数值
    private int limit;
    //当前窗口内计数值
    private int curCounter;


    public SlidingWindowsCounter(int limit, int cycle) {
        //默认窗口大小为10
        this(limit,cycle,cycle>1000?10:2);
    }

    public SlidingWindowsCounter(int limit, int cycle, int windowsSize) {
        if(limit<1||cycle<1||windowsSize<1) {
            throw new IllegalArgumentException();
        }

        windows = new int[windowsSize];
        this.limit = limit;
        this.timeSlice = Math.max(1,cycle/windowsSize);
        preTimeStamp = System.currentTimeMillis();
        curCounter = 0;
    }


    @Override
    public void getTokenWithBlocking() throws InterruptedException {

        //按照当前时间滑动窗口
        sliding();

        synchronized (this) {
            //没有超出限制
            if(curCounter+1<=limit) {
                windows[windows.length-1]++;
                curCounter++;
                return;
            }
        }

        //超出限制,尾递归
        block();
        getTokenWithBlocking();
    }

    @Override
    public boolean getTokenWithoutBlocking() {

        //按照当前时间滑动窗口
        sliding();

        synchronized (this) {
            //没有超出限制
            if(curCounter+1<=limit) {
                windows[windows.length-1]++;
                curCounter++;
                return true;
            }
        }

        //超出限制
        return false;
    }

    //根据当前时间与最久记录时间的差值,将窗口向右滑动n个单位,然后映射到windows中
    private void sliding() {

        //需要向右滑动的单元格个数
        long curTimeStamp = System.currentTimeMillis();
        int n = (int)((curTimeStamp-preTimeStamp)/timeSlice);
        if(n==0) {
            return;
        }

        synchronized (this) {
            //双重检查
            curTimeStamp = System.currentTimeMillis();
            n = (int)((curTimeStamp-preTimeStamp)/timeSlice);
            if(n==0) {
                return;
            }

            //滑动窗口
            int windowsWidth = windows.length;
            int right = (windowsWidth -1) + n;
            int left = Math.max(0,right- windowsWidth +1);
            if(left<=(windowsWidth -1)) {
                System.arraycopy(windows,left,windows,0, windowsWidth -left);
                Arrays.fill(windows, windowsWidth -left, windowsWidth,0);
            } else {
                Arrays.fill(windows,0,windowsWidth,0);
            }

            //更新窗口最左端的时间戳
            preTimeStamp += left * timeSlice;
            //更新当前计数
            curCounter = getCurCounter();
        }
    }

    private int getCurCounter() {
        //计算当前计数总和
        int curCounter = 0;
        for(int counter:windows) {
            curCounter+=counter;
        }
        return curCounter;
    }

    //当前线程陷入睡眠直到空出计数
    private void block() throws InterruptedException {
        int index = 0;
        for(;index<windows.length;index++) {
            if(windows[index]>0) break;
        }
        long waitTime = (index+1) * timeSlice;
        Thread.sleep(waitTime);
    }

}
